package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-6-19
 * Time: 上午10:14
 * To change this template use File | Settings | File Templates.
 */
public class N_Queens_II {
    public int RST=0;
    public boolean isSafe(int i,int j,int n,int[][] map){
        int k=-1;
        while(i+k>=0 && i+k<n && j+k>=0 && j+k<n)  //左上
        {
            if(map[i+k][j+k]==1)
                return false;
            k--;
        }
        k=1;
        while(i+k>=0 && i+k<n && j+k>=0 && j+k<n)        // 右下
        {
            if(map[i+k][j+k]==1)
                return false;
            k++;
        }
        k=-1;
        while(i+k>=0 && i+k<n && j-k>=0 && j-k<n)          //  右上
        {
            if(map[i+k][j-k]==1)
                return false;
            k--;
        }
        k=1;
        while(i+k>=0 && i+k<n && j-k>=0 && j-k<n)         //  左 下
        {
            if(map[i+k][j-k]==1)
                return false;
            k++;
        }
        return true;
    }
    public void find(int[][] map,int level,int n){
        int[] flag = new int[n];
        for(int i=0;i<level;i++){
            for(int j=0;j<n;j++)
                if(map[i][j]==1){
                    flag[j]=1;
                    break;
                }
        }
        if(level==n){
           RST++;
        }
        for(int i=0;i<n;i++){
            if(flag[i]==0 && isSafe(level,i,n,map)){
                map[level][i]=1;
                find(map,level+1,n);
                map[level][i]=0;
            }
        }
    }
    public int totalNQueens(int n) {
        int[][] map = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                map[i][j] = 0;
        }

        for(int i=0;i<n;i++){
            map[0][i]=1;
            find(map, 1, n);
            map[0][i]=0;
        }
        return RST;
    }
    public static void main(String[] args){
        N_Queens_II n_queens_ii = new N_Queens_II();
        System.out.println(n_queens_ii.totalNQueens(1));
    }
}
